// https://leetcode.cn/problems/swap-adjacent-in-lr-string/
// Created by ade on 2022/10/8.
// 在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个"LX"替换一个"XL"，或者用一个"XR"替换一个"RX"。现给定起始字符串start和结束字符串end，请编写代码，当且仅当存在一系列移动操作使得start可以转换成end时， 返回True。
//根据题意，我们每次移动要么是将 XL 变为 LX，要么是将 RX 变为 XR，而该两者操作可分别看做将 L 越过多个 X 向左移动，将 R 越过多个 X 向右移动。
//
//因此在 start 和 end 中序号相同的 L 和 R 必然满足坐标性质：
//
//序号相同的 L : start 的下标不小于 end 的下标（即 L 不能往右移动）
//序号相同的 R : start 的下标不大于 end 的下标（即 R 不能往左移动）
//其中「序号」是指在 LR 字符串中出现的相对顺序。
#include <string>
#include <iostream>

using namespace std;

class Solution {
public:
    // 基本思路：L和R是不能相互调换的，并且start的L的位置必须在end的右面， start的R的位置必须在end的左侧
    bool canTransform(string start, string end) {
        int i = 0, j = 0, n = start.size();// L 和 R的数量
        while (i < n || j < n) {
            while (start[i] == 'X') i++;
            while (end[j] == 'X') j++;
            if (i == n || j == n) return i == j;// 其中一个已经结束，另一个比必须结束
            if (start[i] != end[j]) return false;
            if (start[i] == 'L' && i < j) return false;
            if (start[i] == 'R' && i > j) return false;
            i++;
            j++;
        }

        return i == j;
    }
};

int main() {
    Solution so;
    string s1 = "LXXLXRLXXL"; // ""
    string s2 = "XLLXRXLXLX";
    cout << so.canTransform(s1, s2);
    return 0;
}